The present invention relates to encoding and decoding methods and devices, and an image processing apparatus using the same.
In image coding for a conventional image equipment, a method of performing actual arithmetic coding after the frequency distribution of generated symbols are calculated in units of states to obtain a cumulative probability value required for arithmetic encoding is known. As an example of such multi-valued or multialphabet arithmetic coding, a method described in IEICE transaction IE96-9 (1996-05), the Institute of Electronics, Information and Communication Engineers is known.
In the above article, arithmetic coding using approximation by some parts per the n-th power of 2 is adopted. The contents of this coding will be explained below. (Probability Approximation Algorithm)
Let N be the number of types of symbols to be encoded, and p.sub.i (0.ltoreq.i.ltoreq.N-1) be the probability of occurrence of symbol i. When a probability is approximated by some parts per the n-th power of 2, a probability approximation parameter Q'.sub.i for symbol i is determined by: ##EQU1## where [X] is the integral part of X. The same applies to the following description.
Assume that an approximate probability is determined in descending order of indices, i.e., from i=N-1 to 0, and Q'.sub.i =1 is set when p.sub.i .gtoreq.0 and Q'.sub.i &lt;1.
Since actual encoding/decoding uses an cumulative approximate probability, an cumulative approximate probability parameter Q.sub.i is calculated from Q'.sub.i by: ##EQU2##
In this way, since a probability approximation error is carried over to the approximate probability of the next symbol, probability errors do not accumulate. Also, since processing for determining the approximate probability from symbols with lower occurrence probabilities is used together, the approximate probability of a symbol with a low probability of occurrence can be prevented from becoming 0 or less.
(Encoding Algorithm)
The actual encoding sequence will be described below. Let N be the number of types of symbols to be encoded, and the probability be approximated by some parts per the n-th power of 2. The cumulative approximate probability parameter Q'.sub.i has already been calculated by equations (1) and (2) above. Note that the register length used in arithmetic operations is V=2n bits. This is because the number of effective digits requires 2n bits since an n-bit multiplication is done upon calculating augend A.
The encoding process algorithm is as follows.
[S11] Initialization EQU C.rarw.0, A.rarw.2.sup.n -1
[S12] Encode Symbol k EQU A.sub.0 .rarw.A.times.Q.sub.k-1 EQU A.rarw.(Q.sub.k -Q.sub.k-1) EQU C.rarw.C+A.sub.0 EQU for Q.sub.k-1 =0 when k=0.
[S13] Renormalize
A is shifted to the right until its upper n bits become 0.fwdarw.the number of times of shift is r.
C is shifted to the left by n-r bits to determine the bit overflowing from the register as a code output.
[S12] and [S13] repeat themselves for all the symbols. The final contents of register C are output, thus ending encoding.
(Decoding Algorithm)
The decoding process algorithm is substantially the same as encoding, and is as follows.
[S21] Initialization
C.rarw.V bits from the beginning of a code sequence EQU A.rarw.2.sup.n -1 PA1 Minimum k that satisfies C'&lt;Q.sub.k is the decoded symbol. PA1 for Q.sub.k -1=0 when k=0.
[S22] Calculate Decoded Symbol EQU C'.rarw.[C/A]
[S23] Subtract from Code Sequence EQU C.rarw.C-A.times.Q.sub.k-1 EQU A.rarw.A.times.(Q.sub.k -Q.sub.k-1)
[S24] Renormalize
A is shifted to the right until its upper n bits become 0.fwdarw.the number of times of shift is r.
C is shifted to the left by n-r bits, and in synchronism with bit shift, a code sequence is input to register C from its LSB and is determined to be a code input.
In the above reference, encoding and decoding are done in this way. With this method, arithmetic operations are made using an identical cumulative probability value for an image for at least one frame.
However, since this method can only attain average coding throughout the sequence, it cannot optimally encode an information source, the symbols of which change from the middle of the sequence.
As one scheme for solving this problem, dynamic probability estimation may be adopted to improve coding efficiency. As such dynamic coding, the following method is known. That is, in case of, e.g., abinary information source, the MAX and MIN values of the accumulated frequencies of input symbols are obtained, and when each of MAX and MIN value has exceeded a preset value, the accumulation frequency of each symbol is nearly halved to adjust the adaptation rate (see U.S. Pat. No. 5,025,258).
However, when adaptation of a binary information source is directly applied to multi-valued information, that adaptation must be done in units of bits of multi-valued information, and adjustment of adaptation rate takes place frequently, resulting in too long an encoding/decoding time.